/*
 * @lc app=leetcode.cn id=218 lang=cpp
 *
 * [218] 天际线问题
 */
#include "include.h"
// @lc code=start
typedef pair<int,int> P;
struct cmp
{
    bool operator()(const P p1,const P p2)
    {
        if(p1.first==p2.first) return p1.second>p2.second;
        else return p1.first>p2.first;
    }
};
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> ans;
        priority_queue<pair<int, int>> max_heap;
        // <高度, 右端>
        int i = 0, len = buildings.size();
        int cur_x, cur_h;
        while (i < len || !max_heap.empty()) {
            if (max_heap.empty() || i < len && 
            buildings[i][0] <= max_heap.top().second) {
                cur_x = buildings[i][0];
                while (i < len && cur_x == buildings[i][0]) {
                    max_heap.emplace(buildings[i][2], buildings[i][1]);
                    ++i;
                }
            } else {
                cur_x = max_heap.top().second;
                while (!max_heap.empty() && cur_x >= max_heap.top().second) {
                max_heap.pop();
                }
            }
            cur_h = (max_heap.empty()) ? 0 : max_heap.top().first;
            if (ans.empty() || cur_h != ans.back()[1]) {
                ans.push_back({cur_x, cur_h});
            }
        }
        return ans;
    }
//     vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
//         vector<vector<int>> result;
//         if (buildings.size() == 0){
//             return result;
//         }
//         // 最简单粗暴的办法就是先过一遍，建个起点到终点长的数组
//         // 然后刷一边，最后过一遍数组取结果
//         // 可能会太长了爆掉么。。。

//         // 果然还是按优先队列吧，每个整数点看要不要塞进去或拿出来楼顶

//         // 但还是不方便，直接存下所有起点终点得了

//         // 然而这果然还是太过愚蠢，用priority_queue的话就没法从中间去掉一项
//         // 用map也要遍一次

//         // 看了答案，只需要管右侧，在高度刷新并且右侧更右的时候插入队列
        
//         // 似乎对于pair不能用greater<int>
//         // ??? 卧槽能用greater<P>这样的啊
//         // 其实没必要，自己用struct重载()做成仿函数更简单一些
//         // priority队列会确保cmp(top , bootom) = 。。。啥呢
//         priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> leftQueue;
//         priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> rightQueue;
//         priority_queue<pair<int, int>> heightQueue;

//         for (int i=0;i<buildings.size();++i){
//             leftQueue.push(make_pair(buildings[i][0], i));
//             rightQueue.push(make_pair(buildings[i][1], i));
//         }

//         // just like a -1 node
//         heightQueue.push(make_pair(0, -1));

//         while (!rightQueue.empty()){
//             P leftPair;
//             if (leftQueue.empty()){
//                 leftPair = {INT32_MAX, -1};
//             }else {
//                 leftPair = leftQueue.top();
//             }
//             P rightPair = rightQueue.top();

//             int currentTop = heightQueue.top().first;
//             int currentTopId = heightQueue.top().second;
//             int currentTopRight = buildings[currentTopId][1];

//             // printf("emm \n");
//             // push/left or pop/right
//             if (leftPair.first <= rightPair.first){
//                 int nextPos = leftPair.first;
//                 int id = leftPair.second;
//                 int height = buildings[id][2];
//                 int right = buildings[id][1];

//                 // 只在更高或更右时插入队列
//                 // if (height>currentTop or right>currentTopRight){
//                 //     heightQueue.push(make_pair(height, id));
//                 //     if (height>currentTop){
//                 //         vector<int> point = {nextPos, height};
//                 //         result.emplace_back(point);
//                 //     }
//                 // }

//                 // 更高，插入并且记录插入点
//                 if (height>currentTop){
//                     heightQueue.push(make_pair(height, id));
//                     vector<int> point = {nextPos, height};
//                     result.emplace_back(point);
//                     printf("point (%d, %d)\n", point[0], point[1]);
//                 }
//                 // 更右，只插入队列
//                 if (right>currentTopRight){
//                     heightQueue.push(make_pair(height, id));
//                 }
//                 // 这个左顶点用完了
//                 leftQueue.pop();
//             }else{
//                 int nextPos = rightPair.first;
//                 int id = rightPair.second;
//                 int height = buildings[id][2];

//                 // printf("check %d %d %d %d\n", nextPos, id, height, currentTop);

//                 // 上一步只插入了更高或者更右的，这里需要查它属于哪种
//                 // 有可能后来插入的又高又右

//                 // 只在这个右顶点过后确实导致高度下降时视为结果点

//                 // 这个右顶点小于最高，无事发生啊
//                 if (height < currentTop){
//                     ;
//                 }
//                 // 就是这个，有些复杂，需要考虑之前高度队列里没删掉的过期点
//                 if (height == currentTop){
// popping:
//                     heightQueue.pop();
//                     // 注意是不是空了
//                     int newHeight = 0;
//                     int newId = -1;
//                     int newRight = INT32_MAX;
//                     if (!heightQueue.empty()){
//                         newHeight = heightQueue.top().first;
//                         newId = heightQueue.top().second;
//                         newRight = buildings[newId][1];
//                     }
//                     // 是一个没用的高度，接着删
//                     // printf("right %d %d id %d\n", newRight, nextPos, newId);
//                     if (newRight < nextPos){
//                         goto popping;
//                     }
//                     // 是这个点
//                     if (newHeight < currentTop){
//                         vector<int> point = {nextPos, newHeight};
//                         result.emplace_back(point);
//                         printf("point (%d, %d)\n", point[0], point[1]);
//                     }
//                 }

//                 rightQueue.pop();
//             }
//         }
//         return result;
//    }
};
// @lc code=end
int main(){
    vector<vector<int>> myTest{
        {2,9,10},
        {3,7,15},
        {5,12,12},
        {15,20,10},
        {19,24,8}
    };
    Solution mySolution;
    mySolution.getSkyline(myTest);
    return 0;
}
